package lanQiaoBei.基础算法.sort;

import java.io.*;
/*
* ”第k个数“（快速选择算法）
* 给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。

输入格式
第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在 1∼1e9 范围内），表示整数数列。

输出格式
输出一个整数，表示数列的第 k 小数。

数据范围
1≤n≤100000,
1≤k≤n
输入样例：

8 1
2 4 1 5 3 8 7 6

输出样例：
3
* */
public class P5 {
    static int N;
    static int k;
    public static void main(String[]args) throws Exception{
        int[] arr = scan();
        quick_select(0,N-1,arr);
        System.out.println(arr[k-1]);
    }
    public static void quick_select(int l,int r,int[]arr){
           if(l>=r)return;
           int x=arr[l],i=l-1,j=r+1;
           while(i<j){
                do i++;while(arr[i]<x);
                do j--;while(arr[j]>x);
                if(i<j)swap(i,j,arr);
           }
           if(k-1<=j) quick_select(l,j,arr);
           else quick_select(j+1,r,arr);
    }

    private static void swap(int i, int j,int[] arr) {
            int t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;
    }

    public static int[]scan() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        N=Integer.parseInt(s[0]);
        k=Integer.parseInt(s[1]);
        s= br.readLine().split(" ");
        int[] arr=new int[N];
        for (int i = 0; i < s.length; i++) {
            arr[i]=Integer.parseInt(s[i]);
        }
        return arr;
    }
}
